package com.ljc;

import com.ljc.dto.TreeNode;

import java.util.Random;

/**
 * @author clj
 * @date 2022/12/5
 * @desc
 * 平衡二叉查找树
 *
 * Given an integer array nums where the elements are sorted in ascending order,
 * convert it to a height-balanced binary search tree.
 *
 * Example 1:
 * Input: nums = [-10,-3,0,5,9]
 * Output: [0,-3,9,-10,null,5]
 * Explanation: [0,-10,5,null,-3,null,9] is also accepted:
 *
 * Example 2:
 * Input: nums = [1,3]
 * Output: [3,1]
 * Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.
 */
public class E108ConvertSortedArrayToBinaryTree {
    /**
     * 备注：二叉搜索树的中序遍历是升序序列，题目给定的数组是按照升序排序的有序数组，因此可以确保数组是二叉搜索树的中序遍历序列。
     * 给定二叉搜索树的中序遍历，是否可以唯一地确定二叉搜索树？答案是否定的。
     * 如果没有要求二叉搜索树的高度平衡，则任何一个数字都可以作为二叉搜索树的根节点，因此可能的二叉搜索树有多个。
     * 二叉树：中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树
     * 如果增加一个限制条件，即要求二叉搜索树的高度平衡，是否可以唯一地确定二叉搜索树？答案仍然是否定的。
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] nums = {-10, -3, 0, 5, 9};
        TreeNode a = sortedArrayToBst1(nums);
        TreeNode b = sortedArrayToBst2(nums);

        System.out.println("a: " + a);
        System.out.println("b: " + b);

        TreeNode c1 = sortedArrayToBst3(nums);
        System.out.println("c1: " + c1);
        TreeNode c2 = sortedArrayToBst3(nums);
        System.out.println("c2: " + c2);
        TreeNode c3 = sortedArrayToBst3(nums);
        System.out.println("c3: " + c3);
        TreeNode c4 = sortedArrayToBst3(nums);
        System.out.println("c4: " + c4);

        System.out.println("rand: " + rand.nextInt(2));
        System.out.println("rand: " + rand.nextInt(2));
        System.out.println("rand: " + rand.nextInt(2));

    }

    /**
     * 方法一：中序遍历，总是选择中间位置左边的数字作为根节点
     * 选择中间位置左边的数字作为根节点，则根节点的下标为 mid=(left+right)/2，此处的除法为整数除法。
     */
    public static TreeNode sortedArrayToBst1(int[] nums) {
        return helper1(nums, 0, nums.length - 1);
    }

    public static TreeNode helper1(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        // 总是选择中间位置左边的数字作为根节点
        int mid = (left + right) / 2;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper1(nums, left, mid - 1);
        root.right = helper1(nums, mid + 1, right);
        return root;
    }

    /**
     * 方法二：中序遍历，总是选择中间位置右边的数字作为根节点
     * 选择中间位置右边的数字作为根节点，则根节点的下标为 mid=(left+right+1)/2，此处的除法为整数除法。
     */
    public static TreeNode sortedArrayToBst2(int[] nums) {
        return helper2(nums, 0, nums.length - 1);
    }

    public static TreeNode helper2(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        // 总是选择中间位置右边的数字作为根节点
        int mid = (left + right + 1) / 2;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper2(nums, left, mid - 1);
        root.right = helper2(nums, mid + 1, right);
        return root;
    }


    /**
     * 方法三：中序遍历，选择任意一个中间位置数字作为根节点
     * 选择任意一个中间位置数字作为根节点，则根节点的下标为 mid=(left+right)/2 和 mid=(left+right+1)/2 两者中随机选择一个，
     * 此处的除法为整数除法。
     */
    static Random rand = new Random();

    public static TreeNode sortedArrayToBst3(int[] nums) {
        return helper3(nums, 0, nums.length - 1);
    }

    public static TreeNode helper3(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        //int nextInt(int num) : 随机返回一个值在[0,num)的int类型的整数,包括0不包括num
        // 选择任意一个中间位置数字作为根节点
        int mid = (left + right + rand.nextInt(2)) / 2;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper3(nums, left, mid - 1);
        root.right = helper3(nums, mid + 1, right);
        return root;
    }



}
